class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None


class Solution:
  def buildTree(self, preorder: list, inorder: list) -> TreeNode:
    # 重点在这里：当前序遍历序列为空时，代表已经越过叶子节点
    if len(preorder) == 0:
      return None

    tree_node = TreeNode(preorder[0])  # 根节点
    inorder_index_M = inorder.index(preorder[0])

    inorder_L = inorder[:inorder_index_M]
    inorder_R = inorder[inorder_index_M + 1:]

    preorder_L = preorder[1:len(inorder_L) + 1]
    preorder_R = preorder[len(inorder_L) + 1:]

    tree_node.left = self.buildTree(preorder_L, inorder_L)
    tree_node.right = self.buildTree(preorder_R, inorder_R)
    return tree_node


def print_result(res: TreeNode):
  # 前序遍历二叉树的一个测试方法
  if res == None:
    return
  print(res.val, end=' ')
  print_result(res.left)
  print_result(res.right)


'''
STATUS: LEARNT
TRIES:  N/A
TIME:   276 MS
MEMORY: 88 MB
'''
if __name__ == "__main__":
  solution = Solution()
  preorder = [3, 9, 20, 15, 7]
  inorder = [9, 3, 15, 20, 7]
  # preorder = [7, 9, 12, 13, 10, 15, 20]
  # inorder = [12, 9, 13, 7, 15, 10, 20]
  res = solution.buildTree(preorder, inorder)
  print('---RESULT---')
  print_result(res)
